In recent years, with the wide-spread of cloud computing, there has been a rapid expansion of services based on user's data stored in computational resources connected to networks. In such services, there are more opportunities for handling sensitive data of the user. Therefore, it is becoming important to assure users that the user's data is being securely managed.
Under such environments, research and development are being actively promoted for techniques to manage data in an open network environment while the data is still encrypted and to perform searching, statistical processing, and so on without decrypting the data.
There has also recently been an increase in crime exploiting vulnerabilities in personal authentication that uses passwords or magnetic cards, which has heretofore been employed. Therefore, biometric authentication technology having a greater degree of security based on a biometric feature, such as fingerprints or veins, is drawing attention.
In biometric authentication, in order to verify authentication information, it is necessary to store a template related to biological information in a database. The biological information, for example, information on fingerprints or veins, is data that basically does not change over a person's lifetime. When the biological information is leaked, serious damage may occur as a result. Therefore, biological information is information requiring the highest level of confidentiality. Thus, it is necessary to prevent “impersonation”, for example, even when the template is leaked.
In view of this, there is a need for a type of biometric authentication technology that protects the template, in which the authentication is performed while keeping the template information concealed.
For example, in Patent Document 1, there is disclosed a method in which biometric authentication is performed using, as a template, data obtained by representing fingerprint data as points on a polynomial expression and adding random points to the points to conceal the fingerprint data.
However, in the method disclosed in Patent Document 1, it is known that there is a problem regarding whether or not the biological information is protected with sufficient strength when biometric authentication is repeated many times.
In Non Patent Document 1, there is disclosed a method in which biological information is protected by masking a template stored in a database through a random Bose-Chaudhuri-Hocquenghem (BCH) code word.
In the technology disclosed in Non Patent Document 1, a biometric authentication template is generated in the following manner by using biological information Z and confidential information S.
(A1) The confidential information S is subjected to BCH error-correction coding to generate a code word C.
(A2) An exclusive OR between the code word C and the biological information Z, namely, W1=C(+)Z, is calculated (where the symbol (+) is an operator indicating a bitwise exclusive OR).
(A3) A hash value W2=H (S) is calculated by inputting the confidential information S to a cryptographic hash function H, for example, a secure hash algorithm (SHA) 1.
(A4) The exclusive OR W1 and the hash value W2 are stored in a database as template information.
Verification of whether or not the template generated as described in (A1) to (A4) and other biological information Z′ have been obtained from the same person may be performed as follows.
(B1) An exclusive OR C′ between the exclusive OR W1 and the other biological information Z′, namely, C=W1(+)Z′, is calculated.
(B2) The exclusive OR C′ is input to an error-correcting algorithm with a BCH code to calculate S′.
(B3) The hash value W2 is read from the database, and it is checked whether or not W2=H(S′) is satisfied. When W2=H(S′) is satisfied, it is determined that the template and the biological information Z′ have been obtained from the same person. When W2=H(S′) is not satisfied, it is determined that the template and the biological information Z′ have been obtained from different persons.
The technology described above is a method that does not depend on how the biological information Z is obtained. Therefore, in general, that technology may be regarded as a method of performing matching of whether or not the encrypted text of concealed (encrypted) data is within a fixed Hamming distance to the presented data, without decrypting the concealed (encrypted) data.
As a matching method for data that is still encrypted, there are known methods that use searchable encryption in which deterministic common-key encryption or public-key encryption is used. However, in general, those methods require the keyword to be used in the search to be unique. When matching is performed as described above by using biological information, it is known that the obtained biological information is not always the same due to noise that is included when the biological information is acquired. Therefore, there are difficulties in applying searchable encryption to a method in which biological information is verified.
In Patent Document 2, there is disclosed an encrypted text verification system capable of, in encrypted text verifying, avoiding leaks regarding source plaintext and guaranteeing data security. The encrypted text verification system disclosed in Patent Document 2 includes a registration auxiliary data generation unit, an encrypted text subtraction unit, and a match determination unit. The registration auxiliary data generation unit is configured to generate first auxiliary data and second auxiliary data for verifying, for a first encrypted text in which input data to be concealed is encrypted and registered in a storage device and a second encrypted text in which input data to be verified is encrypted, that a Hamming distance of plaintext between the first encrypted text and the second encrypted text is a predetermined value or less set in advance. The encrypted text subtraction unit is configured to calculate a difference between the first encrypted text registered in the storage device and the second encrypted text. The match determination unit is configured to determine, by using the first and second auxiliary data, whether or not the Hamming distance corresponding to the difference between the first encrypted text and the second encrypted text is a predetermined value or less set in advance.